\mode<article>{
\chapter{Teknik Perencanaan Dinamis}
}

\mode*

\ifthenelse{\boolean{adaTIU}}{
	\begin{footnotesize}
	  \begin{description}
	    \item[Tujuan Pembelajaran]:
	    \begin{itemize}
				\item Memberikan penjelasan mengenai algoritma yang menggunakan teknik Perencanaan Dinamis dan masalah yang dapat diselesaikan dengan teknik tersebut
				\item Memberikan penjelasan mengenai Koefisien Binomial
				\item Memberikan penjelasan mengenai Perkalian Matriks Berantai
				\item Memberikan penjelasan mengenai Algoritma Warshall
				\item Memberikan penjelasan mengenai Algoritma Floyd
			\end{itemize}
			\item[Setelah menyelesaikan modul ini mahasiswa diharapkan dapat]:
			\begin{itemize}
				\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas Pencarian Koefisien Binomial
				\item Menjelaskan masalah Perkalian Matriks Berantai
				\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas Perkalian Matriks Berantai
				\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas Algoritma Warshall
				\item Menuliskan algoritma, membuat program dan menurunkan kompleksitas Algoritma Floyd
			\end{itemize}
			\item[Kata kunci]:
			Teknik Perencanaan Dinamis, Koefisien Binomial, Perkalian Matriks Berantai, Algoritma Warshall, Algoritma Floyd
		\end{description}
	\end{footnotesize}
}

\section{Pendahuluan}

%\dropping{2}{T}
Teknik Perencanaan Dinamis merupakan terjemahan dari kata bahasa Inggris \index{dynamic programming@\emph{Dynamic programming}} \emph{\textbf{Dynamic Programming}}. Istilah ini tidak diartikan sebagai pemrograman dalam artian membuat program komputer, sebab kata ini pada awalnya memang tidak berhubungan dengan teknik pemrograman komputer yang lazim dikenal pada saat ini. Kata \emph{programming} lebih dekat kepada makna "perencanaan", yang berasal dari bidang ilmu Teknik Sipil. Dalam sebuah proyek pembangunan gedung, seringkali rencana awal yang sudah disusun harus berubah karena munculnya faktor-faktor yang didapatkan selama proyek berjalan. Dalam situasi semacam itu rencana awal yang telah disusun secara dinamis harus diubah agar proyek pembangunan gedung tetap dapat dilanjutkan. Pengubahan rencana secara dinamis seperti ini disebut sebagai \emph{dynamic programming}.

Konsep perubahan rencana dalam contoh di atas diadaptasi ke dalam ilmu komputer untuk memecahkan beberapa bentuk masalah komputasi. Dalam memecahkan sebuah masalah komputasi, sebuah rencana untuk mendapatkan solusi harus disusun. Ketika rencana tersebut dijalankan, akan muncul pemecahan-pemecahan yang dapat mengubah rencana awal tersebut. Dalam ilmu komputer, teknik perencanaan dinamis dilakukan dengan menggunakan pemecahan dari sub-problem yang ada untuk digunakan dalam memecahkan sub-problem yang lain.

\mode<all>{
\begin{frame}
Sebuah algoritma perencanaan dinamis memenuhi sifat-sifat berikut:
\begin{enumerate}
	\item Mengkarakterisasikan struktur dari solusi optimal.
	\item Secara rekursif mendefinisikan nilai dari solusi optimal.
	\item Menghitung nilai dari solusi optimal secara \emph{bottom-up}.
	\item Membangun solusi optimal dari informasi yang telah dihitung.
\end{enumerate}
\end{frame}
}

Contoh pengunaan teknik perencanaan dinamis yang banyak dikenal adalah dalam mencari \index{bilangan fibonacci@bilangan Fibonacci} \index{fibonacci@Fibonacci} bilangan \textbf{Fibonacci}. Dengan didefiniskan bahwa bilangan Fibonacci pertama dan kedua masing-masing adalah adalah 0 dan 1, maka dapat dicari bilangan Fibonacci ketiga, selanjutnya dengan bilangan Fibonacci ketiga dapat dicari bilangan Fibonacci keempat dan seterusnya yang secara umum dapat ditulis sebagai:
\mode<all>{
\begin{frame}
\[
F(n) = \left\{ \begin{array}{ll}
F(n-1) + F(n-2) & \mathrm{untuk} \ n \geq 2 \\
1 & {\rm untuk } \ n = 1 \\
0 & {\rm untuk } \ n = 0 \\
\end{array}
\right.
\]
\end{frame}
}
Dari rumus umum ini dapat kita perhatikan bahwa untuk menghitung bilangan Fibonacci pada urutan tertentu kita perlu menghitung bilangan Fibonacci pada urutan sebelumnya. Kita menggunakan hasil yang telah didapat sebelumnya untuk memberikan jawaban berikutnya yang lebih kompleks.

\begin{figure}
  \begin{center}
	  \includegraphics{fib-tree}
	  \label{fig:fib-tree} \caption{Penggunaan teknik perencanaan dinamis dalam mencari bilangan Fibonacci.}
	\end{center}
\end{figure}

Untuk mencari bilangan Fibonacci keempat, maka kita perlu mencari bilangan-bilangan Fibonacci yang lain seperti ditunjukkan dalam Gambar~\ref{fig:fib-tree}. Untuk mendapatkan jawabannya, masalah tersebut dipecah menjadi sub-problem $F(3)$ dan $F(2)$. Pada gilirannya, masing-masing sub-problem tersebut dipecah lagi menjadi sub-problem $F(2), F(1)$ dan $F(1), F(0)$. Perhatikan bahwa untuk mencari bilangan Fibonacci keempat, kita perlu menghitung beberapa bilangan Fibonacci yang lain beberapa kali, seperti $F(2)$ dalam gambar.

Jika kita memecahkannya dengan teknik \emph{Divide and Conquer}, maka kita melakukan proses komputasi yang sama berulang-ulang. Cara ini tentu saja menjadikan pendekatan \emph{divide and conquer} menjadi tidak efisien. Teknik Perencanaan Dinamis menghindari ketidakefisienan seperti ini dengan melakukan pencatatan dari pemecahan-pemecahan sub-problem yang sudah diselesaikan.

Semua masalah komputasi yang dipecahkan dengan teknik Perencanaan Dinamis dalam bab ini menggunakan setidaknya satu struktur data yang digunakan untuk mencatat pemecahan-pemecahan dari seluruh sub-problem yang telah diselesaikan. Ketika pemecahan tersebut diperlukan untuk memecahkan masalah dari sub-problem di bagian lain, maka algoritma Perencanaan Dinamis hanya perlu melakukan \emph{look up} terhadap struktur data tersebut.

Contoh lain masalah komputasi yang menggunakan teknik perencanaan dinamis antara lain adalah \index{bilangan faktorial} \index{faktorial} bilangan faktorial\footnote{Beberapa literatur menyebut bilangan ini sebagai bilangan fakultatif.}, pencarian koefisien binomial, perkalian matriks berantai, algoritma Warshall dan Floyd dalam pencarian jalan terpendek (\emph{shortest path}) antara verteks-verteks yang ada pada suatu graf. Masing-masing masalah tersebut dibahas dalam sub-bab berikut ini, kecuali bilangan faktorial yang dijadikan sebagai bahan latihan (lihat Latihan~\ref{exercise:faktorial} dan~\ref{exercise:fibonacci}).


\section{Pencarian Koefisien Binomial}

Di sekolah menengah, kita pernah mempelajari tentang persamaan kuadrat, yang secara umum bisa dinyatakan sebagai
\[
(a+b)^2
\]
Persamaan ini jika dijabarkan akan menjadi
\[
(a+b)^2 = a^2 + 2ab + b^2
\]

Pangkat $2$ di dalam persamaan tersebut bisa digeneralisasi dengan bilangan bulat $n$. Pertanyaan yang menarik untuk diajukan adalah seperti apa penjabaran dari perpangkatan $(a+b)$ dengan $n$.
\[
(a+b)^n 
\]
Struktur perpangkatan ini dapat diberikan secara detil dengan rumus umum berikut:
\begin{equation} \label{eq:persamaan-kuadrat}
(a+b)^n = C_{i}(n,i) a^{n}b^{0} + \dots + C_{i}(n,i) a^{n-i}b^{i} + \dots + C_{i}(n,n) a^{0}b^{n}
\end{equation}
dengan $0 \leq i \leq n$.

Koefisien-koefisien $C_{i}$ pada persamaan tersebut didapatkan dengan mencari nilai dari 

\index{koefisien binomial@Koefisien Binomial} Koefisian Binomial tidak lain adalah koefisien dari setiap suku $(a + b)^n$ yang secara manual dapat dicari dengan \index{segitiga pascal@Segitiga Pascal} \index{pascal@Pascal!segitiga} \textbf{segitiga Pascal}. Dengan mengamati Tabel~\ref{tbl:koefisien-binomial}, di mana suku awal disebut sebagai suku ke $0$, maka koefisien binomial ke - $k$ pada $(a + b)^n$ dapat dinyatakan sebagai~\cite{levitin}:
% MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later!
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaaiaadoeacaGGOaGaamOBaiaacYcacaWGRb
% Gaaiykaiabg2da9maaceaabaqbaeqabiGaaaqaaiaadoeacaGGOaGa
% amOBaiabgkHiTiaaigdacaGGSaGaam4AaiabgkHiTiaaigdacaGGPa
% Gaey4kaSIaam4qaiaacIcacaWGUbGaeyOeI0IaaGymaiaacYcacaWG
% RbGaaiykaiaacYcaaeaacaqG1bGaaeOBaiaabshacaqG1bGaae4Aai
% aabccacaaIWaGaeyipaWJaam4AaiabgYda8iaad6gaaeaacaaIXaGa
% aiilaaqaaiaabccacaqG1bGaaeOBaiaabshacaqG1bGaae4Aaiaabc
% cacaWGRbGaeyypa0JaaGimaiaabccacaqGHbGaaeiDaiaabggacaqG
% 1bGaaeiiaiaadUgacqGH9aqpcaWGUbaaaaGaay5Eaaaaaa!6495!
\begin{equation} \label{eq:koefisien-binomial}
C(n,k) = \left\{ {\begin{array}{ll}
   {C(n - 1,k - 1) + C(n - 1,k),} & {{\rm untuk } \ 0 < k < n}  \\
   {1,} & {{\rm  untuk } \ k = 0 \ {\rm  atau } \ k = n}  \\
\end{array}} \right.
\end{equation}
% MathType!End!2!1!

Jika gunakan rumus tersebut untuk mencari penjabaran dari bentuk kuadrat $(a+b)^{2}$, kita menggunakan nilai $n = 2$ dalam rumus umum persamaan kuadrat~\ref{eq:persamaan-kuadrat}. Sehingga nilai $i$ yang mungkin adalah $0 \leq i \leq 2$ atau $i = 0, 1, 2$. Jika kita masukkan ke dalam Persamaan~\ref{eq:persamaan-kuadrat} dapat dijabarkan sebagai berikut:
\[
\begin{array}{rcl}
(a+b)^2 & = & C(2,0)a^{2}b^{0} + C(2,1)a^{2-1}b^{1} + C(2,2)a^{2-2}b^{2} \\
        & = & 1 \cdot a^2 + 2 \cdot ab + 1 \cdot b^2 \\
\end{array}
\]
Koefisien $C(2,0)$ dan $C(2,2)$ berdasarkan rumus Persamaan~\ref{eq:koefisien-binomial} nilainya adalah $1$. Yang perlu dijabarkan lebih lanjut adalah koefisien $C(2,1)$:
\[
\begin{array}{rcl}
	C(2,1) & = & C(2-1,1-1)+C(2-1,1) \\
	       & = & C(1,0)+C(1,1) \\
	       & = & 1 + 1 \\
	       & = & 2 \\
\end{array}
\]

\begin{figure}
\begin{center}
\begin{tabular}{ccccccccccccc}
$n$ &     &     &     &     &      &     &      &     &     &     &     & $k$ \\
	\hline
$0$ &     &     &     &     &      & $1$ &      &     &     &     &     & $0$ \\
$1$ &     &     &     &     & $1$  &     & $1$  &     &     &     &     & $1$ \\
$2$ &     &     &     & $1$ &      & $2$ &      & $1$ &     &     &     & $2$ \\
$3$ &     &     & $1$ &     & $3$  &     & $3$  &     & $1$ &     &     & $3$ \\
$4$ &     & $1$ &     & $4$ &      & $6$ &      & $4$ &     & $1$ &     & $4$ \\
$5$ & $1$ &     & $5$ &     & $10$ &     & $10$ &     & $5$ &     & $1$ & $5$ \\
\end{tabular}
\end{center}
\caption{Koefisien Binomial.} \label{fig:koefisien-binomial}
\end{figure}

\begin{table}
\begin{center}
\caption{Tabel Koefisien Binomial~\cite{levitin}.} \label{tbl:koefisien-binomial}
\begin{tabular}{|c|c|c|c|c|c|c|c|}
	\hline
			& 0 & 1 & 2 & \(\ldots\) & \(k-1\) & \(k\) & \(\ldots\) \\
	\hline
		0 & 1 &  &  &  &  &  &  \\
		1 & 1 & 1 &  &  &  &  &  \\
		2 & 1 & 2 & 1 &  &  &  &  \\
		3 & 1 & 3 & 3 & 1 &  &  &  \\
		4 & 1 & 4 & 6 & 4 & 1 &  &  \\
		\(\ldots\) &  &  &  &  &  &  &  \\
		\(k\) & 1 &  &  &  &  & 1 &  \\
		\(\ldots\) &  &  &  &  &  &  &  \\
		\(n-1\) & 1 &  &  &  & \(C(n-1, k-1)\) & \(C(n-1, k)\) &  \\
		\(n\) & 1 &  &  &  &  & \(C(n, k)\) &  \\
	\hline
\end{tabular}
\end{center}
\end{table}

\begin{frame}
\mode<presentation>{Algoritme Koefisien Binomial}
\begin{figure}
\begin{algorithmic}[1]
	\STATE \textsc{KoefisienBinomial} $(n, k)$
	\STATE \COMMENT lakukan sebanyak $(n+1)$ kali
	\FOR{$i=0$ to $n$}
		\STATE $min \leftarrow min(i,k)$
		\FOR{$j=0$ to $min$}
			\STATE \COMMENT Beri nilai $C(n,0)$ dan $C(n,n)$ dengan nilai $1$
			\IF{$j=0$ or $j=k$}
				\STATE $C[i,j] \leftarrow 1$
			\ELSE
				\STATE $C(i,j) \leftarrow C(i-1,j-1) + C(i-1,j)$
			\ENDIF
		\ENDFOR
	\ENDFOR
	\STATE return $C(i,j)$
\end{algorithmic}
\caption{Algoritma Pencarian Koefisien Binomial~\cite{levitin}.} \label{alg:koefisien-binomial}
\end{figure}
\end{frame}

Dalam pemrograman, koefisien $C$ dalam persamaan~\ref{eq:koefisien-binomial} dapat diimplementasikan dengan menggunakan array dua dimensi.
Berdasarkan hal tersebut dapat dibuat algoritma pencarian koefisien binomial seperti pada Algoritme~\ref{alg:koefisien-binomial}.


\section{Perkalian Matriks Berantai}

\emph{Matrix Chain Multiplication} \index{Matrix Chain Multiplication} \index{matriks} \index{Perkalian Rantai Matriks} atau perkalian matriks berantai, merupakan perkalian dari dua atau lebih matriks yang memenuhi syarat. \textbf{\emph{Matrix-chain multiplication problem}} (``Masalah perkalian rantai-matriks'') dapat dinyatakan sebagai berikut: diketahui rangkaian \(\langle A_1, A_2, \ldots A_n \rangle\) matriks, di mana untuk harga \(i = 1, 2, \ldots n\), matriks \(A_i\) memiliki dimensi \(p_{i-1} \times p_i\), letakkan tanda kurung di antara rangkaian matriks tersebut sehingga jumlah perkalian skalar yang dibutuhkan menjadi minimum.

Bila dua buah mariks \(A_1\) dan \(A_2\) dikalikan, maka hanya akan satu cara dalam melakukan perkalian tersebut, tetapi bila tiga buah matriks \(A_1\), \(A_2\) dan \(A_3\) akan dikalikan, maka terdapat dua cara untuk melakukan operasi tersebut, yaitu:
\begin{enumerate}
\item Mengalikan \(A_1\) dengan \(A_2\), kemudian matriks hasil perkalian tersebut dikalikan dengan \(A_3\), atau \((A_1 \times A_2) \times A_3\).
\item Mengalikan \(A_1\) dengan hasil perkalian \(A_2\) dan \(A_3\) atau \(A_1 \times (A_2 \times A_3)\).
\end{enumerate}

Perkalian matriks yang melibatkan lebih dari dua buah matriks memiliki sifat asosiatif. Sifat asosiatif dari perkalian mengatakan bahwa urutan pengerjaan perkalian tidak berpengaruh terhadap hasil perkalian, bagaimanapun urutan perkalian dikerjakan, hasil akhirnya akan selalu sama. Hal ini juga berlaku pada perkalian skalar antara bilangan-bilangan nyata.

Bila kita memiliki tiga buah matriks \(M_a\), \(M_b\), dan \(M_c\), maka berlaku sifat asosiatif berikut ini:

\begin{equation}
	M_a \times ( M_b \times M_c ) = ( M_a \times M_b ) \times M_c
\end{equation}

Bila dilakukan perkalian \(A_1 \times A_2 \times A_3\) dengan kedua cara tersebut, maka hasil perkaliannya adalah sama, namun usaha yang dilakukan memerlukan jumlah operasi aritmatika (perjumlahan dan perkalian) mungkin berbeda. Hal tersebut tentunya ini menyebabkan waktu pemrosesan yang berbeda.

Bila kita ingin mengalikan dua buah matriks \(M_a\) dan \(M_b\), syarat pertama yang harus dipenuhi adalah dimensi kolom dari matriks \(M_a\) harus sama dengan dimensi baris dari matriks \(M_b\). Bila hal ini tidak dipenuhi, maka perkalian kedua buah matriks tidak dapat dilakukan.

\begin{equation}
\begin{array}{cc}
	M_a & M_b \\
	p \times q & q \times r \\
\end{array}
\end{equation}
Misalkan matriks \(M_a\) memiliki ukuran baris dan kolom \(p \times q\), sedangkan matriks \(M_b\) memiliki dimensi \(q \times r\), maka perkalian antara kedua matriks tersebut dapat dilakukan. Hasil perkalian kedua matriks ini adalah sebuah matriks baru \(M_c\) yang memiliki dimensi \(p \times r\).

Dua buah matriks \(M_a\) dan \(M_b\) yang masing-masing memiliki elemen-elemen seperti diilustrasikan di bawah ini, akan membutuhkan perkalian skalar sebanyak \(p \times q \times r\).
\begin{equation}\label{eq:perkalian-umum-matriks}
  \left(
\begin{array}{cccc}
	a_{1,1} & a_{1,2} & \ldots & a_{1,q} \\
	a_{2,1} & a_{2,2} & \ldots & a_{2,q} \\
	\vdots  & & \ddots & \vdots \\
	a_{p,1} & a_{p,2} & \ldots & a_{p,q} \\
\end{array}
  \right)
  \times
  \left(
\begin{array}{cccc}
	b_{1,1} & b_{1,2} & \ldots & b_{1,r} \\
	b_{2,1} & b_{2,2} & \ldots & b_{2,r} \\
	\vdots  & & \ddots & \vdots \\
	b_{q,1} & b_{q,2} & \ldots & b_{q,r} \\
\end{array}
  \right)
\end{equation}
Perkalian matriks pada Persamaan~\ref{eq:perkalian-umum-matriks} akan menghasilkan sebuah matriks baru \(M_c\) yang elemen-elemennya adalah seperti pada Persamaan~\ref{eq:hasil-perkalian-umum-matriks} berikut ini:
\begin{equation}\label{eq:hasil-perkalian-umum-matriks}
  \left(
\begin{array}{ccc}
	a_{1,1} \cdot b_{1,1} + a_{1,2} \cdot b_{2,1} + \ldots + a_{1,q} \cdot b_{q,1}
	  & \ldots
	  & a_{1,1} \cdot b_{1,r} + a_{1,2} \cdot b_{2,r} + \ldots + a_{1,q} \cdot b_{q,r} \\
	a_{2,1} \cdot b_{1,2} + a_{2,2} \cdot b_{2,2} + \ldots + a_{2,q} \cdot b_{q,2}
	  & \ldots
	  & a_{2,1} \cdot b_{2,r} + a_{2,2} \cdot b_{2,r} + \ldots + a_{2,q} \cdot b_{q,r} \\
	\vdots  & \ddots & \vdots \\
	a_{p,1} \cdot b_{1,1} + a_{p,2} \cdot b_{2,1} + \ldots + a_{p,q} \cdot b_{q,r}
	  & \ldots
	  & a_{p,1} \cdot b_{1,r} + a_{p,2} \cdot b_{2,r} + \ldots + a_{p,q} \cdot b_{q,r} \\
\end{array}
  \right)
\end{equation}
Seperti dapat kita lihat, setiap elemen dalam matriks \(M_c\) dihasilkan dari \(q\) buah perkalian skalar antara elemen-elemen matriks \(M_a\) sepanjang barisnya (ada \(q\) elemen) dan elemen-elemen matriks \(M_b\) sepanjang kolomnya. Keseluruhan elemen matriks \(M_c\) ada \(p \times r\) buah, yang masing-masingnya melibatkan \(q\) perkalian skalar. Sehingga total perkalian skalar yang diperlukan untuk mengalikan dua matriks \(M_a\) yang berukuran \(p \times q\) dan matriks \(M_b\) yang berukuran \(q \times r\) adalah \(p \times r \times q\).

Misalkan kita diberikan 3 buah matriks untuk dikalikan, \(A_1\), \(A_2\) dan \(A_3\) masing-masing berukuran \((10 \times 100)\), \((100 \times 5)\) dan \((5 \times 50)\). Bila dilakukan perkalian \(A_1 (10 \times 100)\) dengan \(A_2 (100 \times 5)\) terlebih dahulu, maka diperlukan waktu untuk perkalian yang sebanding dengan \(10 \times 100 \times 5 = 5000\) perkalian untuk menghasilkan matriks berukuran \(10 \times 5\) (lihat algoritma perkalian matriks). Selanjutnya bila matriks tersebut dikalikan dengan \(A_3 (5 \times 50)\), maka diperlukan waktu sebanding dengan \(10 \times 5 \times 50 = 2500\) perkalian. Sehingga total waktu yang diperlukan untuk menghitung \(A_1 \times A_2 \times A_3\) dengan cara \((A_1 \times A_2) \times A3\) adalah sebanding dengan 7500 waktu perkalian. Bila dilakukan dengan cara \(A_1 \times (A_2 \times A_3)\) maka dapat dihitung bahwa diperlukan waktu sebanding dengan 75000 waktu perkalian atau 10 kali lebih lama.

Bila perkalian dilakukan pada jumlah rantai matriks yang lebih banyak maka akan terdapat banyak kemungkinan cara melakukan operasi perkalian berantai tersebut. Dapat dibuktikan bahwa cara untuk melakukan perkalian berantai terhadap \(n\) buah matriks yang memenuhi syarat adalah sebanyak:
\begin{equation} \label{eq:jumlah-kemungkinan-perkalian-matriks}
P(n) = \left\{
\begin{array}{lc}
	1 & \mathrm{untuk} \ n \leq 2 \\
	\Sigma_{k=1}^{n-1} P(k) \cdot P(n-k) & \mathrm{untuk} \ n > 2
\end{array}
\right.
\end{equation}

Jadi untuk mengalikan empat buah rantai matriks \(A_1\), \(A_2\), \(A_3\) dan \(A_4\) terdapat 5 cara sedangkan untuk mengalikan lima buah rantai matriks \(A_1\), \(A_2\), \(A_3\), \(A_4\) dan \(A_5\) terdapat 14 cara. Semakin banyak rantai matriks, maka semakin banyak cara untuk menyelesaikannya. Karena hal tersebut, maka timbul pertanyaan cara manakah yang dapat dilakukan dengan usaha yang minimal, yang juga berarti dalam waktu tercepat untuk perkalian matriks tersebut. Untuk dapat mengevaluasi hal tersebut, perlu dilihat kembali algoritma dari perkalian dua buah matriks \(A_x\) dan \(A_y\) masing-masing dengan ukuran \((i \times k)\) dan \((k \times j)\) yang menghasilkan matriks dengan ukuran \((i \times j)\).

Algoritma perkalian matriks memperlihatkan bahwa waktu yang diperlukan untuk mengalikan dua buah matriks yaitu \(A_x\) berukuran \((i \times k)\) dan \(A_y\) berukuran \((k \times j)\) adalah jumlah dari waktu yang diperlukan untuk melakukan \(i \times j\) insisialisasi ditambah dengan \(i \times k \times j\) waktu penjumlahan dan \(i \times k \times j\) waktu perkalian. Karena waktu yang diperlukan untuk perkalian jauh lebih lama dari perjumlahan, dapat dikatakan bahwa waktu yang diperlukan untuk perkalian dua matriks sangat ditentukan dari jumlah perkalian yang dilakukan, yaitu sebanyak \(i \times k \times j\) buah perkalian. Sehingga \(m_{[x,y]}\), yaitu waktu yang diperlukan untuk mengalikan matriks \(A_x\) dan \(A_y\) dapat didekati atau sebanding dengan waktu yang diperlukan untuk melakukan \(i \times k \times j\) buah perkalian, dimana \(i\) adalah jumlah baris matriks \(A_x\), \(k\) jumlah kolom matriks \(A_x\) (atau jumlah baris matriks \(A_y\)) dan \(j\) jumlah kolom matriks \(A_y\).

Dari syarat perkalian matriks dapat diketahui bahwa maka jumlah kolom matriks yang merupakan anggota rantai matriks selalu sama dengan jumlah baris dari anggota berikutnya. Dengan demikian pada perkalian rantai matriks dapat dibentuk suatu array \(p\) yang dapat mencerminkan ukuran dari setiap anggota rantai matriks.  Sebagai contoh dari rantai perkalian \(A_1 \times A_2 \times A_3\) dapat dibentuk array yang terdiri atas \(p_{0}p_{1}p_{2}p_{3}\), dimana \(p_{0}\) adalah jumlah baris \(A_{1}\), \(p_{1}\) adalah jumlah baris \(A_{2}\) (juga jumlah kolom \(A_{1}\)), \(p_{2}\) adalah jumlah baris \(A_{3}\) (juga jumlah kolom \(A_{2}\)) dan \(p_{3}\) adalah jumlah kolom \(A_{3}\).

Bila suatu rantai matriks terdiri atas \(A_i, \ldots A_k, A_{k+1}, \ldots A_j\) ingin dikalikan, maka ukuran dari matriks tersebut dapat disimpan dalam suatu array \(p\) yang terdiri atas \(p_{i-1}p_i \ldots p_{k-1} p_k p_{k+1} \ldots p_{j-1} p_j\). Untuk dapat mengalikannya, rantai matriks dibagi menjadi dua rantai matriks yang lebih pendek yaitu \(A_i, \ldots A_k\) yang bila dikalikan akan membentuk matriks \(A_x\) dengan ukuran \((p_{i-1} \times  p_k)\) dan \(A_{k+1}, \ldots A_j\) yang bila dikalikan akan membentuk matriks \(A_y\) dengan ukuran \((p_k \times p_j)\).

Dengan waktu yang diperlukan untuk melakukan perkalian rantai matriks tersebut adalah:
\[
m_{[i, j]} = m_{[i,k]} + m_{[k+1, j]} + p_{i-1} \times p_k \times p_j
\]
Karena ada sejumlah $k$ kemungkinan, maka waktu minimum untuk melakukan operasi perkalian rantai matriks tersebut adalah:
\[
\mathrm{min} \ (m_{[i, j]}) = \mathrm{min}_{k=i}^{j-1} ( m_{[i,k]} + m_{[k+1, j]} + p_{i-1} \cdot p_{k} \cdot p_{j} )
\]
Mudah dimengerti waktu yang diperlukan untuk melakukan perkalian pada rantai matriks yang terdiri atas hanya satu matriks satu (yaitu $A_{n}$), dengan perkataan lain bahwa $m_{[n,n]}$ akan selalu bernilai nol.

Dengan demikian waktu minimum untuk mengalikan rantai matriks $A_{i}$ sampai dengan $A_{j}$ dapat ditulis sebagai:
\[
m_{[i, j]} = \mathrm{min} ( m_{[i,k]} + m_{[k+1, j]} + p_{i-1} \cdot p_{k} \cdot p_{j} )
\]
untuk $i < j$, dengan $i \leq k < j$ , dimana bila $i = j$ , maka waktu yang diperlukan adalah $m_{[i,i]} = m_{[j, j]} = 0$.

Dari contoh diatas dapat diketahui bahwa waktu tercepat yang diperlukan untuk mengalikan matriks $A_1 \times A_2 \times A_3$, dimana $p_0 = 10$, $p_1 = 100$, $p_2 = 5$, $p_3 = 50$, adalah minimal dari:

Cara 1: 
\[
m_{[1,3]} = m_{[1,1]} + m_{[2,3]} + p_{0}p_{1}p_{3}
\]
dimana $m_{[2,3]}$ adalah $m_{[2,2]} + m_{[3,3]} + p_{1}p_{2}p_{3}$. Sehingga
\[
m_{[1,3]} = m_{[1,1]} + m_{[2,2]} + m_{[3,3]} + p_{1}p_{2}p_{3} + p_{0}p_{1}p_{3}
\]
\[
m_{[1,3]} = 0 + 0 + 0 + 100 \cdot 5 \cdot 50 + 10 \cdot 100 \cdot 50 = 75000
\]


Cara 2:
\[
m_{[1,3]} = m_{[1,2]} + m_{[3,3]} + p_{0}p_{2}p_{3}
\]
dimana $m_{[1,2]}$ adalah $m_{[1,1]} + m_{[2,2]} + p_{0}p_{1}p_{2}$, sehingga
\[
m_{[1,3]} = m_{[1,1]} + m_{[2,2]} + p_{0}p_{1}p_{2} + m_{[3,3]} + p_{0}p_{2}p_{3}
\]
\[
m_{[1,3]} = 0 + 0 + 0 + 10 \cdot 100 \cdot 5 + 0 + 10 \cdot 5 \cdot 50 = 7500
\]
Dari kedua cara tersebut dapat terlihat bahwa cara kedua jauh lebih cepat daripada cara pertama.

Jumlah kemungkinan untuk mengalikan rantai matriks akan semakin besar apabila jumlah matriksnya semakin banyak. Oleh karena itu akan semakin sulit untuk mencari cara tercepat di antara semua kemungkinan yang ada. Algoritma untuk mencari alternatif yang memberikan waktu tercepat dapat dibuat dengan melihat kenyataan bahwa waktu tercepat dari semua kemungkinan $m_{[i, j]}$ yang ada dapat dirumuskan sebagai berikut
\begin{equation} \label{eq:mij-minimum}
m_{[i,j]} = \left\{
\begin{array}{ll}
	0 & \mathrm{untuk} \ i = j \\
	\mathrm{min}_{k=1}^{j-1} \ ( m_{[i,k]} + m_{[k+1, j]} + p_{i-1} \cdot p_{k} \cdot p_{j} ) & \mathrm{untuk} \ i < j \\
\end{array}
\right.
\end{equation}

Oleh karena itu algoritma yang dilakukan tidak lain adalah mencari $k$ yang dapat memberikan waktu tercepat. Selanjutnya dengan $k$ tersebut rantai matriks akan terbagi dua, dan pada setiap bagian dicari lagi tempat yang tepat untuk membagi dua setiap bagian di mana dapat dihasilkan waktu tercepat. Demikian seterusnya hingga akan didapat rantai matriks yang terdiri atas satu atau dua matriks yang telah dapat dicari jumlah perkalian yang diperlukan.

Masukan untuk algoritma ini adalah array $p$ yang terdiri atas $n+1$ anggota ($n$ adalah jumlah matriks dalam rantai matriks yang akan dikalikan) yang mencerminkan ukuran dari anggota rantai matriks. Sedangkan keluaran dari algoritma ini adalah matriks $s$ dan $m$, di mana $s_{[i, j]}$ akan berisi integer $k$ yang menunjukkan tempat di mana rantai matriks dibagi menjadi dua rantai matriks yang lebih pendek yang akan memberikan waktu tercepat. Matriks $m$ akan berisi informasi jumlah operasi perkalian rantai matriks, dimana $m_{[i,j]}$ menunjukkan jumlah perkalian minimum yang diperlukan untuk mengalikan rantai matriks ke $i$ sampai dengan $j$.

Uraian pencarian cara yang dapat memberikan waktu tercepat diatas dituliskan secara algoritmis seperti pada Algoritme~\ref{alg:matrix-chain-multiplication}.

\begin{algorithm}
  \begin{algorithmic}[1]
		\STATE \textsc{CaraPerkalianMatriksBerantai} $(p_{[0..n]})$
		\STATE //matriks yang dikalikan adalam matriks $A_{0}$ hingga $A_{n-1}$
		\STATE $m_{[i,i]} \leftarrow  s_{[i,i]} \leftarrow 0$
		\FOR{$d = 1$ to $n-1$}
			\FOR{$i = 0$ to $n-1-d$}
				\STATE $j \leftarrow i + d$
				\STATE //inisialisasi waktu perkalian $A_{i}$ dengan $A_{j}$ sebagai bilangan takhingga
				\STATE $m[i,j] \leftarrow \infty$
				\FOR{$k = i$ to $j - 1$}
					\STATE $q \leftarrow m_{[i,k]} + m_{[k+1,j]} + p_{i} \times p_{k+1} \times p_{j}$
					\IF{$q < m_{[i,j]}$}
						\STATE //selalu update $q$ dengan waktu perkalian yang lebih kecil
						\STATE $q = m_{[i,j]}$
						\STATE //catat nilai yang memberikan waktu terkecil
						\STATE $s_{[i,j]} = k$
					\ENDIF
				\ENDFOR
			\ENDFOR
		\ENDFOR
		\STATE return $s$
  \end{algorithmic}
	\caption{Algoritma pencarian cara tercepat perkalian matriks berantai. \index{Matrix Chain Multiplication}} \label{alg:matrix-chain-multiplication}
\end{algorithm}

\begin{algorithm}
\begin{algorithmic}[1]
  \STATE \textsc{Matrix-Chain-Order (\(p\))}
  \COMMENT \(p\) adalah array / larik berisi dimensi-dimensi matriks
  \STATE \(n \leftarrow\) length[\(p\)] - 1
  \FOR{\(i \leftarrow 1\) to \(n\)}
    \STATE \(m_{i,i} \leftarrow 0\)
  \ENDFOR
  \FOR{\(l \leftarrow 2\) to \(n\)}
    \FOR{\(i \leftarrow 1\) to \(n - l + 1\)}
      \STATE \(j \leftarrow i + l - 1\)
      \STATE \(m_{i,j} \leftarrow \infty\)
      \FOR{\(k \leftarrow i\) to \(j - 1\)}
        \STATE \(q \leftarrow m_{i,k} + m_{k+1,j} + p_{i-1} p_k p_j \)
        \IF{\(q < m_{i,j}\)}
          \STATE \(m_{i,j} \leftarrow q\)
          \STATE \(s_{i,j} \leftarrow k\)
        \ENDIF
      \ENDFOR
    \ENDFOR
  \ENDFOR
  \STATE return \(m\) and \(s\)
\end{algorithmic}
\caption{Algoritma Matrix-Chain-Order~\cite{cormen}}
\label{alg:alg-matrix-chain-order}
\end{algorithm}

Gambar~\ref{alg:alg-matrix-chain-order} \cite{cormen} menunjukkan langkah-langkah yang dilakukan dengan menggunakan pendekatan \emph{dynamic programming}. Untuk mengetahui jumlah perkalian skalar yang minimum, kita melakukan pendekatan \emph{bottom-up}. Dari setiap pasangan matriks kita dapat mengetahui ongkos optimum (jumlah perkalian skalar minimum) dan menyimpannya dalam sebuah struktur data. Algoritma dalam Gambar~\ref{alg:alg-matrix-chain-order} mengasumsikan sejumlah matriks \(A_i\) yang memiliki dimensi \(p_{i-1} \times p_i\) untuk setiap nilai \(i = 1, 2, \ldots, n\). Masukan bagi algoritma tersebut adalah deretan \(p_0, p_1, p_2, \ldots, p_n\) dengan \emph{length}(\(p\)) \(= n+1\). Lebih lanjut algoritma ini menggunakan bantuan tabel \(m_{[1 \ldots n, 1 \ldots n]}\) untuk menyimpan ongkos \(m_{i,j}\) dan bantuan tabel \(s_{[1 \ldots n, 1 \ldots n]}\) yang mencatat indeks \(k\) yang bisa menghasilkan ongkos optimum untuk menghitung \(m_{i,j}\). Tabel \(m\) dan \(s\) jika divisualisasikan tampak seperti dalam Gambar~\ref{fig:tabel-m} dan Gambar~\ref{fig:tabel-s}.

Entri \(m_{i,j}\) nantinya akan berisi jumlah minimum perkalian skalar yang dibutuhkan untuk melakukan perkalian matriks-matriks \(A_i\) sampai \(A_j\). Baris 3 sampai 5 dari Algoritma~\ref{alg:alg-matrix-chain-order} menginisialisasi isi dari tabel \(m\) dengan nilai 0 untuk nilai-nilai \(j\) yang sama dengan \(i\). Untuk sebuah matriks tunggal, sama sekali tidak diperlukan satu pun perkalian skalar. Entri $m_{i,j}$ dapat dibaca sebagai jumlah perkalian skalar yang dibutuhkan untuk mengalikan rangkaian matriks-matriks $A_i, A_{i+1}, \ldots A_j$. Jika $i = j$ artinya hanya ada satu matriks $A_i$ yang tidak memerlukan perkalian skalar sama sekali. Dengan demikian, entri \(m_{i,j}\) diisi dengan nilai 0 untuk nilai-nilai $i = j$.

\begin{figure}
{\par\centering
  \includegraphics{TabelM}
\par}
\caption[Tabel $m$]{Isi tabel $m$ setelah lengkap diisi.
  Data dalam
  tabel ini diturunkan dari matriks-matriks pada
    Tabel~\ref{tbl:contoh-matriks} dan menggunakan
    Algoritma~\ref{alg:alg-matrix-chain-order}. Baris paling bawah
    pada tabel $m$ ini diisi ketika
    Algoritma~\ref{alg:alg-matrix-chain-order} menginisialisasinya
    pertama kali.}
\label{fig:tabel-m}
\end{figure}

\begin{figure}
{\par\centering
  \includegraphics{TabelS}
\par}
\caption[Tabel $s$]{Isi tabel $s$ setelah lengkap diisi. Data dalam
  tabel ini diturunkan dari matriks-matriks pada
    Tabel~\ref{tbl:contoh-matriks}
  (Halaman~\pageref{tbl:contoh-matriks}) dan menggunakan
    Algoritma~\ref{alg:alg-matrix-chain-order}. Baris paling bawah
    pada tabel $s$ ini diisi ketika
    Algoritma~\ref{alg:alg-matrix-chain-order} menginisialisasinya
    pertama kali.}
\label{fig:tabel-s}
\end{figure}

Baris-baris berikutnya secara sistematis mengisi entri-entri tabel \(m_{i,j}\) dengan data yang sesuai. Baris 9 menginisialisasi entri \(m_{i,j}\) dengan nilai \(\infty\) karena nantinya entri ini akan dibandingkan dengan nilai yang lebih kecil pada loop terdalam (baris 10 sampai 16). Baris 11 menghitung jumlah perkalian skalar yang diperlukan untuk mengalikan matriks-matriks \(A_i\) sampai \(A_j\) dengan `memotong' perkalian matriks pada matriks \(A_k\)
\[ ( A_i \times A_{i+1} \times A_{i+2} \times \ldots \times A_{k-1} \times A_k ) \times ( A_{k+1} \times \ldots A_{j-1} \times A_j ) \]
Setiap kali iterasi pada variabel \(k\), letak `pemotongan' perkalian matriks juga digeser sesuai dengan harga \(k\). Dalam setiap kali iterasi, jumlah perkalian skalar yang dibutuhkan dicatat di dalam variabel \(q\). Harga \(q\) akan selalu dibandingkan dengan nilai di dalam entri \(m_{i,j}\).

Loop terdalam pada baris 10 - 16 sebetulnya sama dengan mencari nilai perkalian skalar minimum dari semua kemungkinan yang ada.
\[
m_{i,j} = \left\{
\begin{array}{lc}
	0 & \mathrm{untuk} \ i = j , \\
	\min_{i \leq k < j} \{ m_{i,k} + m_{k+1,j} + p_{i-1} p_k p_j \} & \mathrm{untuk} \ i < j \\
\end{array}
\right.
\]
Setiap kali berhasil menemukan nilai perkalian skalar yang lebih kecil daripada yang sudah tercatat dalam entri \(m_{i,j}\), entri tabel \(s_{i,j}\) dimutakhirkan dengan nilai \(k\). Maksudnya tidak lain adalah mencatat di mana `pemotongan' harus dilakukan.

Ketika Algoritma~\ref{alg:alg-matrix-chain-order} diterapkan untuk 6 buah matriks seperti dalam Tabel~\ref{tbl:contoh-matriks}, maka isi tabel \(m\) dan \(s\) akan tampak seperti dalam Gambar~\ref{fig:tabel-m} dan~\ref{fig:tabel-s}. Ujilah pemahaman anda tentang uraian yang diberikan dalam subbab ini dengan mengisi tabel \(m\) dan \(s\) yang anda kerjakan sendiri, untuk kemudian dibandingkan dengan hasil yang tercantum dalam kedua gambar tersebut.

\begin{table}
\caption{Enam matriks contoh untuk Gambar~\ref{fig:tabel-m}
  dan~\ref{fig:tabel-s}.}
\label{tbl:contoh-matriks}
{\par\centering
\begin{tabular}{|c|r@{$\times$}l|}
  \hline
    Matriks & \multicolumn{2}{c|}{Dimensi} \\
  \hline
  \hline
    \(A_1\) & \(5\) & \(10\) \\
    \(A_2\) & \(10\) & \(12\) \\
    \(A_3\) & \(12\) & \(3\) \\
    \(A_4\) & \(3\) & \(50\) \\
    \(A_5\) & \(50\) & \(7\) \\
    \(A_6\) & \(7\) & \(5\) \\
  \hline
\end{tabular}
\par}
\end{table}

Telah disebutkan sebelumnya, keluaran dari Algoritma~\ref{alg:alg-matrix-chain-order} adalah tabel \(m\) yang berisi informasi tentang jumlah perkalian skalar minimum yang didapatkan untuk mengalikan matriks-matriks yang diberikan. Di samping itu, algoritma tersebut juga menghasilkan sebuah tabel \(s\), yang berisi informasi tentang di mana tanda kurung harus diletakkan supaya jumlah perkalian skalar yang dilakukan bisa minimum.

Untuk mengetahui bagaimana informasi dalam tabel \(s\) bisa dimanfaatkan, kita lihat contoh pada Gambar~\ref{fig:tabel-s} yang telah terisi lengkap. Data-data dalam tabel itu menginformasikan kepada kita bagaimana kita harus meletakkan kurung di antara 6 matriks yang diberikan pada Tabel~\ref{tbl:contoh-matriks}. Karena kita memiliki enam buah matriks, maka kita harus tahu bagaimana pengelompokan keenam buah matriks ini harus dilakukan. Untuk itu kita lihat entri \(s_{1,6}\) pada tabel \(s\). Entri ini bernilai 3. Itu artinya, untuk menghasilkan perkalian skalar dalam jumlah yang minimum, matriks-matriks \(A_1\) sampai dengan \(A_6\) harus `dipotong' menjadi 2 kelompok, dan perpotongannya terletak pada
matriks \(A_3\):
\[ ( A_1 \times A_2 \times A_3 ) \times ( A_4 \times A_5 \times A_6) \]
Lebih lanjut harus dicari bagaimana kelompok matriks \(A_1\), \(A_2\), dan \(A_3\) dikelompokkan. Untuk itu lihat entri \(s_{1,3}\), yang ternyata bernilai 1. Ini artinya perkalian matriks harus lebih dulu mengerjakan perkalian matriks \(A_2\) dengan \(A_3\), baru kemudian hasilnya dikalikan dengan \(A_1\).

Demikian juga halnya dengan kelompok matriks \(A_4\) sampai \(A_6\), sehingga hasil akhir pengelompokan matriks yang dihasilkan adalah:
\[ ( (A_1) \times ( (A_2) \times (A_3) ) ) \times ( ( (A_4) \times
      (A_5) ) \times (A_6) ) \]

Jika anda amati dengan baik, sifat pemrograman dinamis dari masalah perkalian matriks berantai terletak pada pencarian nilai $m_{i,j}$ dalam setiap tahap. Ambil contoh Gambar~\ref{fig:tabel-m}, untuk mendapatkan nilai $m_{2,5}$ misalnya, maka anda perlu mengetahui nilai-nilai yang sudah didapatkan sebelumnya pada entri-entri $m_{\mathbf{2},2}, m_{\mathbf{2},3}, m_{\mathbf{2},4}$ dan entri-entri $m_{3,\mathbf{5}}, m_{4,\mathbf{5}}, m_{5,\mathbf{5}}$. Lebih jauh lagi, setiap sub-solusi $m_{i,j}$ memiliki peranan dalam mencari sub-solusi yang lebih besar. Entri $m_{2,5}$ pada gilirannya akan digunakan untuk mencari sub-solusi $m_{1,\mathbf{5}}$ dan $m_{\mathbf{2},6}$. Artinya, setiap sub-solusi saling terkait satu sama lain, suatu hal yang tidak didapatkan dalam pendekatan \index{divide and conquer@\emph{divide and conquer}} \emph{divide and conquer} di mana sub-solusi yang satu sama sekali terpisah dari sub-solusi yang lainnya.


\section{Algoritma Warshall}

\index{algoritme warshall@Algoritme \emph{Warshall}} \index{algoritme@Algoritme!warshall@\emph{Warshall}} \textbf{Algoritme \emph{Warshall}} merupakan algoritme yang dapat dipergunakan untuk menentukan apakah ada \emph{path} dari setiap verteks ke verteks lainnya pada suatu graf sembarang. Algoritme ini dibangun atas dasar sifat transitif pada graf berarah, yaitu bila ada \emph{path} dari verteks $a$ ke verteks $b$, dan ada \emph{path} dari verteks $b$ ke verteks $c$, maka tentunya ada \emph{path} dari $a$ ke $c$.

Sebagai keluaran, algoritme ini akan menghasilkan sebuah matriks \index{transitive closure@\emph{transitive closure}} \textbf{\emph{transitive closure}} $A$, yang memperlihatkan ada atau tidaknya \emph{path} dari setiap pasangan verteks $i$ dan $j$ di dalam graf. Jika $a_{i,j} = 1$ berarti ada \emph{path} dari verteks $i$ ke verteks $j$. Sebaliknya jika $a_{i,j} = 0$ berarti tidak ada \emph{path} dari $i$ ke $j$.

Matriks \emph{transitive closure} $A$ didapatkan dari \index{adjacency matrix@\emph{adjacency matrix}} \index{matrix@\emph{matrix}!adjacency@\emph{adjacency}} \emph{adjacency matrix} graf berarah $G$. Informasi keterhubungan pasangan verteks $i$ dengan verteks $j$ didapatkan berdasar sifat transitif yang dijelaskan sebelumnya. Verteks $j$ bisa dicapai dari verteks $i$ jika ada sebuah verteks perantara $k$ yang bisa menghantarkan verteks $i$ ke verteks $k$, dan dari verteks $k$ bisa dilanjutkan ke verteks $j$.
 
Bila saja graf $G$ mula-mula direprsentasikan dengan matriks \emph{adjacency} $A$ yang memperlihatkan ada tidaknya hubungan langsung dari verteks $i$ ke $j$, maka berdasarkan matriks $A$ tersebut, ada atau tidaknya \emph{path} dari $i$ ke $j$, dapat dilihat dari nilai $a_{i,j}$. Ini berlaku jika antara verteks $i$ dan $j$ terhubung langsung. Jika antara $j$ tidak terhubung langsung dari $i$, maka $j$  bisa dicapai dari $i$ jika bisa ditemukan sebuah verteks perantara $k$ sehingga ada \emph{path} dari $i$ ke $k$ dan dari $k$ ke $j$.

Berdasarkan hal tersebut maka didapat suatu ketentuan bahwa ada tidaknya \emph{path} dari verteks $i$ ke $j$ dapat dicari dengan cara mengubah nilai $a_{i,j}$ dengan nilai $a_{i,j} \ {\rm OR} \ (a_{i,k} \ {\rm AND } \ a_{k,j})$, yang dapat ditulis dengan suatu pernyataan logika:
\begin{equation} \label{eq:algoritme-warshall}
a_{i,j} = a_{i,j} \ {\rm OR } \ (a_{i,k} \ {\rm AND } \ a_{k,j})
\end{equation}

Mengingat bahwa matriks \emph{adjacency} asal berukuran $n \times n$ (dengan $n$ adalah jumlah verteks pada graf), maka perubahan nilai $a_{i,j}$ tentu harus dilakukan sebanyak $n$ kali.

Berdasarkan hal tersebut, maka dapat ditulis algoritme Warshall seperti pada Algoritme~\ref{alg:algoritme-warshall}.

\begin{algorithm}
  \begin{algorithmic}[1]
		\STATE \textsc{Warshall} $(W_{[0..n-1, 0..n-1]})$
		\STATE // lakukan sebanyak $n$ kali
		\FOR{$k \leftarrow 0$ to $n - 1$}
			\STATE // lakukan perubahan nilai setiap elemen $W$
			\FOR{$i \leftarrow 0$ to $n - 1$}
				\FOR{$j \leftarrow 0$ to $n - 1$}
					\STATE $W_{[i,j]} \leftarrow W_{[i,j]} \mathrm{OR} \ (W_{[i,k]} \mathrm{AND} \ W_{[k,j]})$
				\ENDFOR
			\ENDFOR
		\ENDFOR
		\STATE Return $W$
  \end{algorithmic}
  \caption{Algoritma Warshall~\cite{levitin}.} \label{alg:algoritme-warshall}
\end{algorithm}

\begin{figure}
	\begin{center}
	\resizebox*{0.3\textwidth}{!}{
	\includegraphics{graf-warshall}
	}
	\caption{Graf berarah untuk contoh algoritme Warshall~\cite{levitin}.} \label{fig:graf-algoritme-warshall}
	\end{center}
\end{figure}

Contoh penerapan algoritme Warshall dapat diberikan pada sebuah graf berarah pada Gambar~\ref{fig:graf-algoritme-warshall}. Secara visual, kita bisa lihat bahwa ada jalur dari verteks $A$ ke verteks $C$ secara tidak langsung. Algoritme Warshall memberikan jawaban apakah memang ada jalur semacam itu pada sebuah graf berarah. Dengan masukan graf pada Gambar~\ref{fig:graf-algoritme-warshall}, langkah pertama kita mulai membuat matriks \emph{adjacency} dari graf tersebut. Matriks ini kita beri nama matriks $R^0$ yang menunjukkan bahwa kita masih ada pada iterasi ke-$0$ dari algoritme Warshall. Kita akan melakukan iterasi sebanyak $4$ kali, sesuai dengan jumlah verteks yang ada di dalam graf yang diberikan. Langkah-langkah yang dilakukan untuk mendapatkan matriks \emph{transitive closure} digambarkan dalam Gambar~\ref{fig:iterasi-algoritme-warshall}.

\begin{figure}
	\begin{center}
	\subfigure[]{\resizebox*{0.35\textwidth}{!}{
\(
R^0 \begin{array}{*{20}c}
   {} & {\begin{array}{*{20}c}
   A & B & C & D  \\
\end{array}}  \\
   {\begin{array}{*{20}c}
   A  \\
   B  \\
   C  \\
   D  \\
\end{array}} & {\left( {\begin{array}{*{20}c}
   \colorbox{gray}{0} & \colorbox{gray}{1} & \colorbox{gray}{0} & \colorbox{gray}{0}  \\
   \colorbox{gray}{0} & 0 & 0 & 1  \\
   \colorbox{gray}{0} & 0 & 0 & 0  \\
   \colorbox{gray}{1} & 0 & 1 & 0  \\
\end{array}} \right)}  \\
\end{array}
\)
	} \label{subfig:iterasi-algoritme-warshall-r0}}
	\subfigure[]{\resizebox*{0.35\textwidth}{!}{
% MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later!
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaaiaadkfadaahaaWcbeqaaiaaigdaaaGcfa
% qabeGacaaabaaabaqbaeqabeabaaaabaGaamyqaaqaaiaadkeaaeaa
% caWGdbaabaGaamiraaaaaeaafaqabeabbaaaaeaacaWGbbaabaGaam
% OqaaqaaiaadoeaaeaacaWGebaaaaqaamaabmaabaqbaeqabqabaaaa
% aeaacaaIWaaabaGaaGymaaqaaiaaicdaaeaacaaIWaaabaGaaGimaa
% qaaiaaicdaaeaacaaIWaaabaGaaGymaaqaaiaaicdaaeaacaaIWaaa
% baGaaGimaaqaaiaaicdaaeaacaaIXaaabaGaaGymaaqaaiaaigdaae
% aacaaIWaaaaaGaayjkaiaawMcaaaaaaaa!4729!
\(
R^1 \begin{array}{*{20}c}
   {} & {\begin{array}{*{20}c}
   A & B & C & D  \\
\end{array}}  \\
   {\begin{array}{*{20}c}
   A  \\
   B  \\
   C  \\
   D  \\
\end{array}} & {\left( {\begin{array}{*{20}c}
   0 & \colorbox{gray}{1} & 0 & 0  \\
   \colorbox{gray}{0} & \colorbox{gray}{0} & \colorbox{gray}{0} & \colorbox{gray}{1}  \\
   0 & \colorbox{gray}{0} & 0 & 0  \\
   1 & \colorbox{gray}{\textbf{1}} & 1 & 0  \\
\end{array}} \right)}  \\
\end{array}
\)
% MathType!End!2!1!
	} \label{subfig:iterasi-algoritme-warshall-r1}}
	\subfigure[]{\resizebox*{0.35\textwidth}{!}{
% MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later!
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaaiaadkfadaahaaWcbeqaaiaaikdaaaGcfa
% qabeGacaaabaaabaqbaeqabeabaaaabaGaamyqaaqaaiaadkeaaeaa
% caWGdbaabaGaamiraaaaaeaafaqabeabbaaaaeaacaWGbbaabaGaam
% OqaaqaaiaadoeaaeaacaWGebaaaaqaamaabmaabaqbaeqabqabaaaa
% aeaacaaIWaaabaGaaGymaaqaaiaaicdaaeaacaaIXaaabaGaaGimaa
% qaaiaaicdaaeaacaaIWaaabaGaaGymaaqaaiaaicdaaeaacaaIWaaa
% baGaaGimaaqaaiaaicdaaeaacaaIXaaabaGaaGymaaqaaiaaigdaae
% aacaaIXaaaaaGaayjkaiaawMcaaaaaaaa!472C!
\(
R^2 \begin{array}{*{20}c}
   {} & {\begin{array}{*{20}c}
   A & B & C & D  \\
\end{array}}  \\
   {\begin{array}{*{20}c}
   A  \\
   B  \\
   C  \\
   D  \\
\end{array}} & {\left( {\begin{array}{*{20}c}
   0 & 1 & \colorbox{gray}{0} & \textbf{1}  \\
   0 & 0 & \colorbox{gray}{0} & 1  \\
   \colorbox{gray}{0} & \colorbox{gray}{0} & \colorbox{gray}{0} & \colorbox{gray}{0}  \\
   1 & 1 & \colorbox{gray}{1} & \textbf{1}  \\
\end{array}} \right)}  \\
\end{array}
\)
% MathType!End!2!1!
	} \label{subfig:iterasi-algoritme-warshall-r2}}
	\subfigure[]{\resizebox*{0.35\textwidth}{!}{
% MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later!
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaaiaadkfadaahaaWcbeqaaiaaiodaaaGcfa
% qabeGacaaabaaabaqbaeqabeabaaaabaGaamyqaaqaaiaadkeaaeaa
% caWGdbaabaGaamiraaaaaeaafaqabeabbaaaaeaacaWGbbaabaGaam
% OqaaqaaiaadoeaaeaacaWGebaaaaqaamaabmaabaqbaeqabqabaaaa
% aeaacaaIWaaabaGaaGymaaqaaiaaicdaaeaacaaIXaaabaGaaGimaa
% qaaiaaicdaaeaacaaIWaaabaGaaGymaaqaaiaaicdaaeaacaaIWaaa
% baGaaGimaaqaaiaaicdaaeaacaaIXaaabaGaaGymaaqaaiaaigdaae
% aacaaIXaaaaaGaayjkaiaawMcaaaaaaaa!472D!
\(
R^3 \begin{array}{*{20}c}
   {} & {\begin{array}{*{20}c}
   A & B & C & D  \\
\end{array}}  \\
   {\begin{array}{*{20}c}
   A  \\
   B  \\
   C  \\
   D  \\
\end{array}} & {\left( {\begin{array}{*{20}c}
   0 & 1 & 0 & \colorbox{gray}{1}  \\
   0 & 0 & 0 & \colorbox{gray}{1}  \\
   0 & 0 & 0 & \colorbox{gray}{0}  \\
   \colorbox{gray}{1} & \colorbox{gray}{1} & \colorbox{gray}{1} & \colorbox{gray}{1}  \\
\end{array}} \right)}  \\
\end{array}
\)
% MathType!End!2!1!
	} \label{subfig:iterasi-algoritme-warshall-r3}}
	\subfigure[]{\resizebox*{0.35\textwidth}{!}{
% MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later!
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaaiaadkfadaahaaWcbeqaaiaaisdaaaGcfa
% qabeGacaaabaaabaqbaeqabeabaaaabaGaamyqaaqaaiaadkeaaeaa
% caWGdbaabaGaamiraaaaaeaafaqabeabbaaaaeaacaWGbbaabaGaam
% OqaaqaaiaadoeaaeaacaWGebaaaaqaamaabmaabaqbaeqabqabaaaa
% aeaacaaIXaaabaGaaGymaaqaaiaaigdaaeaacaaIXaaabaGaaGymaa
% qaaiaaigdaaeaacaaIXaaabaGaaGymaaqaaiaaicdaaeaacaaIWaaa
% baGaaGimaaqaaiaaicdaaeaacaaIXaaabaGaaGymaaqaaiaaigdaae
% aacaaIXaaaaaGaayjkaiaawMcaaaaaaaa!4733!
\(
R^4 \begin{array}{*{20}c}
   {} & {\begin{array}{*{20}c}
   A & B & C & D  \\
\end{array}}  \\
   {\begin{array}{*{20}c}
   A  \\
   B  \\
   C  \\
   D  \\
\end{array}} & {\left( {\begin{array}{*{20}c}
   \textbf{1} & 1 & \textbf{1} & 1  \\
   \textbf{1} & \textbf{1} & \textbf{1} & 1  \\
   0 & 0 & 0 & 0  \\
   1 & 1 & 1 & 1  \\
\end{array}} \right)}  \\
\end{array}
\)
% MathType!End!2!1!
	} \label{subfig:iterasi-algoritme-warshall-r4}}
	\caption{Langkah-langkah pencarian matriks transitive closure dengan algoritme Warshall~\cite{levitin}.} \label{fig:iterasi-algoritme-warshall}
	\end{center}
\end{figure}

Dalam setiap iterasi, kita akan memeriksa setiap verteks $k$ di dalam graf (baris 3 pada Algoritme~\ref{alg:algoritme-warshall}), apakah $k$ dapat menjadi perantara antara sembarang pasangan verteks $i$ dan $j$ sehingga $i$ dapat mencapai $j$ melewati $k$. Pada iterasi kedua, kita mencari verteks-verteks yang terhubung secara tidak langsung melalui verteks $A$. Secara visual, kita bisa lihat dari Gambar~\ref{fig:graf-algoritme-warshall} bahwa pasangan verteks yang menggunakan $A$ sebagai perantara adalah verteks $D$ dan verteks $B$. Secara algoritmis, kita ubah informasi pada matriks $R^0_{D,B}$ dari $0$ menjadi $1$ dengan Persamaan~\ref{eq:algoritme-warshall}.

Untuk mengubah matriks $R^0$ menjadi matriks $R^1$, yang kita lakukan adalah menyalin baris $A$ dan kolom $A$ dari $R^0$ ke $R^1$. Secara algoritmis sebenarnya kita menerapkan Persamaan~\ref{eq:algoritme-warshall}, akan tetapi bisa dibuktikan bahwa untuk baris-kolom $A$, entri-entrinya tidak akan berubah. Entri-entri yang mungkin berubah adalah selain baris-kolom $A$ yang masih berisi nilai $0$. Jika entri selain baris-kolom $A$ sudah bernilai $1$ artinya entri tersebut sudah menunjukkan keterhubungan antara pasangan verteks yang diwakili. Sebagai contoh, entri $R^0_{D,C}$ sudah bernilai $1$. Artinya dari verteks $D$ ke verteks $C$ memang sudah ada \emph{path} yang sejauh ini ditemukan.

Perubahan entri dari $0$ di matriks $R^0$ menjadi $1$ di matriks $R^1$ dimungkinkan dengan melihat perpotongan antara baris dan kolom dari entri yang bersangkutan dengan baris-kolom $A$. Sebagai contoh, perubahan entri $R^1_{B,B}$ kita lihat dari perpotongan $R^0_{B,B}$ secara horizontal dengan kolom $A$ (yaitu $R^0_{B,A}$) dan secara vertikal dengan baris $A$ (yaitu $R^0_{A,B}$). Menurut Persamaan~\ref{eq:algoritme-warshall}, entri $R^1_{B,B}$ diberi nilai
\[
\begin{array}{rcl}
R^1_{B,B} & = & R^0_{B,B} \ {\rm OR } \ (R^0_{B,A} \ {\rm AND } \ R^0_{A,B}) \\
          & = & 0 \ {\rm OR } \ (0 \ {\rm AND } \ 0) \\
          & = & 0 \ {\rm OR } \ 0 \\
          & = & 0 \\
\end{array}
\]

Ketujuh entri yang lain kita evaluasi dengan cara yang sama. Satu-satunya yang berubah adalah entri $R^0_{D,B}$. Jika diperhatikan dari matriks $R^0$, entri ini berubah dari $0$ menjadi $1$ karena $R^0_{D,A} = 1$. Ini artinya ada \emph{path} dari verteks $D$ ke verteks $A$. Selanjutnya kita perhatikan bahwa entri $R^0_{A,B}$ juga bernilai $1$. Ini artinya dari verteks $A$ ada \emph{path} ke verteks $B$. Karena ada \emph{path} dari verteks $D$ ke $A$ dan dari verteks $A$ ke $B$, maka berarti ada \emph{path} dari verteks $D$ ke $B$ (melalui verteks $A$).

Pada iterasi kedua kita membuat matriks $R^2$ dengan langkah-langkah yang mirip dengan iterasi pertama. Iterasi kedua ini mencari kemungkinan pasangan verteks yang bisa terhubungkan secara tidak langsung melalui verteks $B$. Yang harus dilakukan pertama kali adalah menyalin baris-kolom $B$ di matriks $R^1$ ke matriks $R^2$. Kemudian semua entri yang sudah bernilai $1$ kita salin dari $R^1$ ke $R^2$. Baru kemudian kita lihat entri-entri yang bernilai $0$ apakah ada kemungkinan berubah menjadi $1$ atau tidak.

Hanya ada dua entri yang berubah pada iterasi kedua ini yaitu entri $R^2_{A,D}$ dan $R^2_{D,D}$. Entri $R^2_{D,D}$ sebelumnya bernilai $0$ karena memang tidak ada \emph{path} yang secara langsung menhubungkan verteks $D$ dengan dirinya sendiri. Namun demikian, pada iterasi kedua ini kita bisa lihat bahwa dari verteks $D$ kita bisa mencapai verteks $B$ (melalui perantaraan verteks $A$ seperti yang sudah kita temukan pada iterasi pertama). Ini sesuai dengan data pada entri $R^1_{D,B}$. Selanjutnya dari verteks $B$ kita bisa menemukan \emph{path} ke verteks $D$ seperti ditunjukkan oleh entri $R^1_{B,D}$. Karena ada \emph{path} dari $D$ ke $B$ dan ada \emph{path} dari $B$ ke $D$, maka bisa disimpulkan bahwa ada \emph{path} dari $D$ ke $D$.

Entri $R^2_{A,D}$ juga bisa dijelaskan dengan cara yang kurang lebih sama.

Pada iterasi ketiga tidak ada perubahan entri sama sekali, seperti ditunjukkan pada Gambar~\ref{subfig:iterasi-algoritme-warshall-r3}. Pada iterasi keeempat atau terakhir, tampak banyak perubahan seperti ditunjukkan Gambar~\ref{subfig:iterasi-algoritme-warshall-r4}. Setelah empat iterasi, kita berhasil mendapatkan matriks \emph{transitive closure} dari graf pada Gambar~\ref{fig:graf-algoritme-warshall}. Hasilnya kita dapatkan bahwa dari semua verteks kita bisa mencapai verteks yang lain kecuali dari verteks $C$ kita tidak bisa mencapai verteks mana pun.


\section{Algoritme Floyd} \label{algoritme-floyd} \label{sect:algoritme-floyd}

\index{algoritme floyd@algoritme Floyd} \index{algoritme!floyd@Floyd} \textbf{Algoritme Floyd} merupakan algoritme yang dapat dipergunakan untuk mencari jarak terpendek dari setiap verteks ke verteks lainnya pada suatu graf, dikenal sebagai masalah \index{all pairs shortest path@\emph{all pairs shortest path}} \index{shortest path@\emph{shortest path}!all pairs@\emph{all pairs}} \textbf{\emph{all pairs shortest paths}}. Sesungguhnya algoritme Floyd ini berdasarkan kenyataan yang sama dengan pembentukan \index{matriks!transitive closure@\emph{transitive closure}} \emph{transitive closure matrix} pada algoritme Warshall. Hal ini mudah dimengerti karena jarak dari suatu verteks ke verteks yang lain hanya akan ada apabila ada \emph{path} dari verteks yang menghubungkan kedua verteks tersebut.

Pencarian jarak terpendek dalam sebuah graf menggunakan sebuah prinsip yang disebut sebagai \index{prinsip relaksasi} \textbf{prinsip relaksasi}, yaitu bila jarak dari verteks $i$ ke verteks $j$ lebih besar dari penjumlahan jarak $i$ ke $k$ dengan jarak $k$ ke $j$, tentu jarak terpendek dari $i$ ke $j$ bukanlah $a_{i,j}$, melainkan $a_{i,k} + a_{k,j}$.

Prinsip relaksasi ini adalah prinsip yang sama dengan yang digunakan pada Algoritme Dijkstra (lihat Subbab~\ref{algoritme-dijkstra}, halaman~\pageref{algoritme-dijkstra}). Perbedaan antara algoritme Dijkstra dengan algoritme Floyd adalah bahwa algoritme Dijkstra memecahkan masalah \emph{single source shortest path}. Masalah \emph{all pairs shortest path} sebenarnya dapat dipecahkan dengan jalan menggunakan algoritme Dijkstra untuk setiap verteks yang ada di dalam graf. Namun cara seperti ini kurang efisien karena tingkat kompleksitasnya yang tinggi (lihat Latihan~\ref{ex:all-pairs-shortest-path-dijkstra}).

Dengan demikian algoritme ini dimulai dengan pembentukan \index{matriks!adjacency@\emph{adjacency}} matriks \emph{adjacency} $A$ di mana elemen matriks tersebut memperlihatkan jarak langsung dari verteks $i$ ke $j$. Bila tidak ada hubungan langsung dari $i$ ke $j$, maka elemen $a_{i,j}$ diisi dengan nilai takhingga ($\infty$).

\begin{figure}
	\begin{center}
	\resizebox*{0.3\textwidth}{!}{
		\includegraphics{relaksasi}
	}
	\caption{\index{prinsip relaksasi} Prinsip relaksasi.} \label{fig:prinsip-relaksasi}
	\end{center}
\end{figure}

\begin{algorithm}
	\begin{algorithmic}[1]
		\IF{$d_{i,j} > d_{i,k} + d_{k,j}$}
			\STATE $d_{i,j} \leftarrow d_{i,k} + d_{k,j}$
		\ENDIF
	\end{algorithmic}
	\caption{Prinsip relaksasi.} \label{alg:prinsip-relaksasi}
\end{algorithm}

Prinsip relaksasi menggunakan ide sederhana untuk mencari jarak terpendek dari sembarang verteks $i$ ke sembarang verteks lain $j$. Perhatikan Gambar~\ref{fig:prinsip-relaksasi} dan Algoritme~\ref{alg:prinsip-relaksasi}, dari verteks $i$ ke verteks $j$ mungkin hanya ada satu \emph{path}. Jika kita bisa menemukan jalur lain dari $i$ ke $j$ melalu verteks $k$, dan jumlah jarak $d(i,k)$ ditambah jumlah jarak $d(k,j)$ lebih kecil daripada jarak langsung $d(i,j)$ dari $i$ ke $j$, maka kita mengubah informasi jarak terpendek dari $i$ ke $j$ adalah melalui verteks $k$.

Berdasarkan ide tersebut, maka algoritme Floyd untuk mencari jarak terpendek dari setiap pasangan verteks dalam sebuah graf dapat ditulis seperti pada Algoritme{alg:algoritme-floyd}.

\begin{algorithm}
\begin{algorithmic}[1]
	\STATE \textsc{Floyd} $(F [0..n-1, 0..n-1])$
	\STATE //lakukan sebanyak \(n\) kali
	\FOR{$k \leftarrow 0$ to $n - 1$}
		\STATE //lakukan perubahan nilai setiap elemen \(W\)
		\FOR{$i \leftarrow 0$ to $n - 1$}
			\FOR{$j \leftarrow 0$ to $n - 1$}
				\IF{$F_{i,j} > F_{i,k} + F_{k,j}$}
					\STATE $F_{i,j} \leftarrow F_{i,k} + F_{k,j}$
				\ENDIF
			\ENDFOR
		\ENDFOR
	\ENDFOR
	\STATE baris 05	Return F
\end{algorithmic}
\caption{Algoritma Floyd.} \label{alg:algoritme-floyd}
\end{algorithm}

Contoh penerapan algoritme Floyd dapat diberikan pada sebuah graf seperti dalam Gambar~\ref{fig:graf-algoritme-floyd}. Seperti telah disebutkan, prinsip yang digunakan dalam algoritme Floyd mirip dengan prinsip yang digunakan dalam algoritme Warshall. Perbedaannya terletak pada pencarian jarak terpendek antara pasangan verteks. Di dalam algoritme Warshall, antara sembarang pasangan verteks $i$ dan $j$ kita menguji apakah ada \emph{path} yang menghubungkan pasangan verteks tersebut. Di dalam algoritme Floyd, di antara sembarang pasangan verteks $i$ dan $j$ kita mencari jarak terpendek di antara pasangan verteks tersebut jika memang ada jarak terpendek yang bisa ditemukan.

\begin{figure}
	\begin{center}
		\resizebox*{0.3\textwidth}{!}{
			\includegraphics{graf-floyd}
		}
		\caption{Graf berarah untuk contoh algoritme Floyd~\cite{levitin}.} \label{fig:graf-algoritme-floyd}
	\end{center}
\end{figure}

\begin{figure}
	\begin{center}
		\subfigure[Adjacency matrix]{\resizebox*{0.35\textwidth}{!}{
% MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later!
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaaiaadseadaahaaWcbeqaaiaaicdaaaGcfa
% qabeGacaaabaaabaqbaeqabeabaaaabaGaamyqaaqaaiaadkeaaeaa
% caWGdbaabaGaamiraaaaaeaafaqabeabbaaaaeaacaWGbbaabaGaam
% OqaaqaaiaadoeaaeaacaWGebaaaaqaamaabmaabaqbaeqabqabaaaa
% aeaacaaIWaaabaGaeyOhIukabaGaaG4maaqaaiabg6HiLcqaaiaaik
% daaeaacaaIWaaabaGaeyOhIukabaGaeyOhIukabaGaeyOhIukabaGa
% aG4naaqaaiaaicdaaeaacaaIXaaabaGaaGOnaaqaaiabg6HiLcqaai
% abg6HiLcqaaiaaicdaaaaacaGLOaGaayzkaaaaaaaa!4C29!
\(
D^0 \begin{array}{*{20}c}
   {} & {\begin{array}{*{20}c}
   A & B & C & D  \\
\end{array}}  \\
   {\begin{array}{*{20}c}
   A  \\
   B  \\
   C  \\
   D  \\
\end{array}} & {\left( {\begin{array}{*{20}c}
   \colorbox{gray}{0} & \infty  & \colorbox{gray}{3} & \infty   \\
   \colorbox{gray}{2} & 0 & \infty  & \infty   \\
   \infty  & 7 & 0 & 1  \\
   \colorbox{gray}{6} & \infty  & \infty  & 0  \\
\end{array}} \right)}  \\
\end{array}
\)
% MathType!End!2!1!
		} \label{subfig:iterasi-algoritme-floyd-d0}}
		\subfigure[Iterasi ke-1]{\resizebox*{0.35\textwidth}{!}{
% MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later!
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaaiaadseadaahaaWcbeqaaiaaigdaaaGcfa
% qabeGacaaabaaabaqbaeqabeabaaaabaGaamyqaaqaaiaadkeaaeaa
% caWGdbaabaGaamiraaaaaeaafaqabeabbaaaaeaacaWGbbaabaGaam
% OqaaqaaiaadoeaaeaacaWGebaaaaqaamaabmaabaqbaeqabqabaaaa
% aeaacaaIWaaabaGaeyOhIukabaGaaG4maaqaaiabg6HiLcqaaiaaik
% daaeaacaaIWaaabaGaaGynaaqaaiabg6HiLcqaaiabg6HiLcqaaiaa
% iEdaaeaacaaIWaaabaGaaGymaaqaaiaaiAdaaeaacqGHEisPaeaaca
% aI5aaabaGaaGimaaaaaiaawIcacaGLPaaaaaaaaa!4ACA!
\(
D^1 \begin{array}{*{20}c}
   {} & {\begin{array}{*{20}c}
   A & B & C & D  \\
\end{array}}  \\
   {\begin{array}{*{20}c}
   A  \\
   B  \\
   C  \\
   D  \\
\end{array}} & {\left( {\begin{array}{*{20}c}
   0 & \infty  & 3 & \infty   \\
   \colorbox{gray}{2} & \colorbox{gray}{0} & \colorbox{gray}{\textbf{5}} & \infty   \\
   \infty  & \colorbox{gray}{7} & 0 & 1  \\
   6 & \infty  & \textbf{9} & 0  \\
\end{array}} \right)}  \\
\end{array}
\)
% MathType!End!2!1!
		} \label{subfig:iterasi-algoritme-floyd-d1}}
		\subfigure[Iterasi ke-2]{\resizebox*{0.35\textwidth}{!}{
% MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later!
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaaiaadseadaahaaWcbeqaaiaaikdaaaGcfa
% qabeGacaaabaaabaqbaeqabeabaaaabaGaamyqaaqaaiaadkeaaeaa
% caWGdbaabaGaamiraaaaaeaafaqabeabbaaaaeaacaWGbbaabaGaam
% OqaaqaaiaadoeaaeaacaWGebaaaaqaamaabmaabaqbaeqabqabaaaa
% aeaacaaIWaaabaGaeyOhIukabaGaaG4maaqaaiabg6HiLcqaaiaaik
% daaeaacaaIWaaabaGaaGynaaqaaiabg6HiLcqaaiaaiMdaaeaacaaI
% 3aaabaGaaGimaaqaaiaaigdaaeaacaaI2aaabaGaeyOhIukabaGaaG
% yoaaqaaiaaicdaaaaacaGLOaGaayzkaaaaaaaa!4A1D!
\(
D^2 \begin{array}{*{20}c}
   {} & {\begin{array}{*{20}c}
   A & B & C & D  \\
\end{array}}  \\
   {\begin{array}{*{20}c}
   A  \\
   B  \\
   C  \\
   D  \\
\end{array}} & {\left( {\begin{array}{*{20}c}
   0 & \infty  & \colorbox{gray}{3} & \infty   \\
   2 & 0 & \colorbox{gray}{5} & \infty   \\
   \colorbox{gray}{\textbf{9}} & \colorbox{gray}{7} & \colorbox{gray}{0} & \colorbox{gray}{1}  \\
   6 & \infty  & \colorbox{gray}{9} & 0  \\
\end{array}} \right)}  \\
\end{array}
\)
% MathType!End!2!1!
		} \label{subfig:iterasi-algoritme-floyd-d2}}
		\subfigure[Iterasi ke-3]{\resizebox*{0.35\textwidth}{!}{
% MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later!
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaaiaadseadaahaaWcbeqaaiaaiodaaaGcfa
% qabeGacaaabaaabaqbaeqabeabaaaabaGaamyqaaqaaiaadkeaaeaa
% caWGdbaabaGaamiraaaaaeaafaqabeabbaaaaeaacaWGbbaabaGaam
% OqaaqaaiaadoeaaeaacaWGebaaaaqaamaabmaabaqbaeqabqabaaaa
% aeaacaaIWaaabaGaaGymaiaaicdaaeaacaaIZaaabaGaaGinaaqaai
% aaikdaaeaacaaIWaaabaGaaGynaaqaaiaaiAdaaeaacaaI5aaabaGa
% aG4naaqaaiaaicdaaeaacaaIXaaabaGaaGOnaaqaaiaaigdacaaI2a
% aabaGaaGyoaaqaaiaaicdaaaaacaGLOaGaayzkaaaaaaaa!48C8!
\(
D^3 \begin{array}{*{20}c}
   {} & {\begin{array}{*{20}c}
   A & B & C & D  \\
\end{array}}  \\
   {\begin{array}{*{20}c}
   A  \\
   B  \\
   C  \\
   D  \\
\end{array}} & {\left( {\begin{array}{*{20}c}
   0 & \textbf{10} & 3 & \colorbox{gray}{\textbf{4}}  \\
   2 & 0 & 5 & \colorbox{gray}{\textbf{6}}  \\
   9 & 7 & 0 & \colorbox{gray}{1}  \\
   \colorbox{gray}{6} & \colorbox{gray}{\textbf{16}} & \colorbox{gray}{9} & \colorbox{gray}{0}  \\
\end{array}} \right)}  \\
\end{array}
\)
% MathType!End!2!1!
		} \label{subfig:iterasi-algoritme-floyd-d3}}
		\subfigure[Iterasi ke-4]{\resizebox*{0.35\textwidth}{!}{
% MathType!Translator!2!1!LaTeX.tdl!TeX -- LaTeX 2.09 and later!
% MathType!MTEF!2!1!+-
% feqaeaartrvr0aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn
% hiov2DGi1BTfMBaeXatLxBI9gBaebbnrfifHhDYfgasaacH8srps0l
% bbf9q8WrFfeuY-Hhbbf9v8qqaqFr0xc9pk0xbba9q8WqFfea0-yr0R
% Yxir-Jbba9q8aq0-yq-He9q8qqQ8frFve9Fve9Ff0dmeaabaqaciGa
% caGaaeqabaaaamaaaOqaaiaadseadaahaaWcbeqaaiaaisdaaaGcfa
% qabeGacaaabaaabaqbaeqabeabaaaabaGaamyqaaqaaiaadkeaaeaa
% caWGdbaabaGaamiraaaaaeaafaqabeabbaaaaeaacaWGbbaabaGaam
% OqaaqaaiaadoeaaeaacaWGebaaaaqaamaabmaabaqbaeqabqabaaaa
% aeaacaaIWaaabaGaaGymaiaaicdaaeaacaaIZaaabaGaaGinaaqaai
% aaikdaaeaacaaIWaaabaGaaGynaaqaaiaaiAdaaeaacaaI3aaabaGa
% aG4naaqaaiaaicdaaeaacaaIXaaabaGaaGOnaaqaaiaaigdacaaI2a
% aabaGaaGyoaaqaaiaaicdaaaaacaGLOaGaayzkaaaaaaaa!48C7!
\(
D^4 \begin{array}{*{20}c}
   {} & {\begin{array}{*{20}c}
   A & B & C & D  \\
\end{array}}  \\
   {\begin{array}{*{20}c}
   A  \\
   B  \\
   C  \\
   D  \\
\end{array}} & {\left( {\begin{array}{*{20}c}
   0 & {10} & 3 & 4  \\
   2 & 0 & 5 & 6  \\
   \textbf{7} & 7 & 0 & 1  \\
   6 & {16} & 9 & 0  \\
\end{array}} \right)}  \\
\end{array}
\)
% MathType!End!2!1!
		} \label{subfig:iterasi-algoritme-floyd-d4}}
	\caption{Langkah-langkah pencarian all pairs shortest path dengan algoritme Floyd~\cite{levitin}.} \label{fig:iterasi-algoritme-floyd}
	\end{center}
\end{figure}

Karena di dalam algoritme Floyd yang kita cari adalah jarak terpendek, bukan ada tidaknya \emph{path}, maka kita mulai dari matriks jarak yang sebenarnya berasal dari matriks \emph{adjacency}, seperti ditunjukkan dalam Gambar~\ref{subfig:iterasi-algoritme-floyd-d0}.

Pada iterasi pertama, kita perlu membentuk matriks $D^1$ dari matriks $D^0$. Cara dan idenya mirip seperti yang kita lakukan pada iterasi di algoritme Warshall. Pada iterasi ini kita akan mencari tahu apakah verteks $A$ dapat memperpendek jarak antara sembarang pasangan verteks. Hal pertama yang kita lakukan adalah menyalin baris-kolom $A$ dari matriks $D^0$ ke matriks $D^1$. Kemudian kita menyalin juga entri-entri yang tidak mungkin berubah. Untuk algoritme Floyd, entri-entri yang tidak mungkin berubah adalah entri-entri pada diagonal utama matriks \emph{adjacency}. Berarti masih ada enam entri di matriks $D^1$ yang mungkin berubah.

Pertama kita lihat entri $D^1_{B,C}$. Di matriks $D^0$, nilai entri ini adalah $\infty$. Sekarang kita perhatikan apakah dari verteks $B$ ke verteks $C$ ada jarak yang lebih pendek jika kita lebih dulu melewati verteks $A$. Jawabannya kita dapatkan dengan lebih dulu menelusuri \emph{path} dari $B$ ke $A$ dengan jarak $2$, kemudian kita lanjutkan dengan menelusuri \emph{path} dari $A$ ke $C$ dengan jarak $3$. Berarti dari verteks $B$ kita bisa mencapai verteks $C$ melalui $A$ dengan jarak $2 + 3 = 5$. Karena jarak ini lebih kecil daripada jarak antara $B$ dan $C$ yang kita ketahui sejauh ini, maka entri $D^1_{B,C}$ kita ubah dari $\infty$ menjadi $5$.

Dengan cara berpikir yang sama, kita juga dapat memeriksa entri $D^1_{B,D}$. Di sini kita lihat dari verteks $B$ kita bisa mencapai verteks $A$ dengan jarak $2$. Akan tetapi dari verteks $A$ ke verteks $D$ belum ada \emph{path} yang bisa digunakan. Sehingga jarak dari $B$ ke $D$ tidak berubah. Hasil iterasi pertama diperlihatkan pada Gambar~\ref{subfig:iterasi-algoritme-floyd-d1}.

Iterasi-iterasi berikutnya ditunjukkan pada Gambar~\ref{subfig:iterasi-algoritme-floyd-d2} hingga~\ref{subfig:iterasi-algoritme-floyd-d4}. Hasil akhir matriks \emph{adjacency} menunjukkan jarak terpendek (\emph{shortest path}) antara semua pasangan verteks yang ada dalam graf pada Gambar~\ref{fig:graf-algoritme-floyd}. Perhatikan bahwa pada iterasi terakhir terdapat perubahan entri $D^4_{C,A}$ dari $9$ menjadi $7$. Nilai entri ini diubah menjadi $9$ ketika kita mengevaluasi apakah ada \emph{path} dari verteks $A$ ke verteks $C$ melalui verteks $B$ (Gambar~\ref{subfig:iterasi-algoritme-floyd-d2}). Pada iterasi terakhir, kita menemukan bahwa dari verteks $C$ ke verteks $A$ bisa didapatkan jarak yang lebih pendek melalui verteks $D$. Hal ini bisa dibuktikan dengan memeriksa secara visual graf dalam Gambar~\ref{fig:graf-algoritme-floyd}.


\section{Latihan}

%\renewcounter{latihan}
\renewcounter{chapter}
\begin{ExerciseList}%[counter={latihan}]
  \Exercise \label{exercise:faktorial} Tulislah sebuah program dalam bahasa pemrograman kesukaan anda untuk memecahkan masalah pencarian nilai faktorial dengan menggunakan teknik Perencanaan Dinamis.
  
  \Exercise \label{exercise:fibonacci} Bilangan Fibonacci seperti yang dibahas dalam awal bab ini dapat diselesaikan dengan setidaknya tiga teknik pemrograman, yaitu secara iteratif dengan menggunakan struktur \emph{loop}, secara rekursif, atau dengan menggunakan teknik perencanaan dinamis.
  
  Buatlah implementasi program untuk mencari bilangan Fibonacci dengan ketiga teknik pemrograman tersebut, dan bandingkan waktu eksekusi yang dibutuhkan untuk mencari bilangan Fibonacci ke-50.
  
  \Exercise Hitunglah kompleksitas algoritma untuk menghasilkan \(k\) kombinasi dari sejumlah \(n\) unsur, \(C(n,k)!\)
  
  \Exercise \label{exercise:algoritme-binomial-rekursif} Dengan mengingat bahwa \(C(n,k) = C(n-1,k-1) + C(n-1,k)\), buatlah algoritma rekursif untuk mencari \(C(n,k)\).
  
  \Exercise Berdasarkan algoritme yang anda buat pada Soal~\ref{exercise:algoritme-binomial-rekursif}, buatlah sebuah fungsi yang mengimplementasikan algoritme tersebut.
  
  \Exercise Carilah koefisien-koefisien berikut ini dengan menggunakan Persamaan~\ref{eq:koefisien-binomial} (jika ada)
	\begin{enumerate}
		\item $C(2,3)$
		\item $C(3,2)$
		\item $C(10,5)$
	\end{enumerate}
	
	\Exercise Gunakan Tabel~\ref{tbl:koefisien-binomial}, Persamaan~\ref{eq:persamaan-kuadrat}, dan Persamaan~\ref{eq:koefisien-binomial} untuk menjabarkan perpangkatan berikut ini:
	\begin{enumerate}
		\item $(a+b)^5$
		\item $(x+3)^4$
	\end{enumerate}
	
	\Exercise Carilah cara untuk mengalikan 6 buah matrix $A$, $B$, $C$, $D$, $E$ dan $F$ yang masing-masing mempunyai ukuran \(500 \times 20\), \(20 \times 300\), \(300 \times 150\), \(150 \times 400\), \(400 \times 50\) dan \(50 \times 100\) yang memberikan waktu tercepat.
	
	\Exercise Turunkan running time Perkalian Matriks Berantai.
	
	\Exercise Apakah algoritme Perkalian Matriks Berantai memberikan manfaat jika diterapkan pada rangkaian $n$ matriks bujursangkar? Jelaskan.
	
	\Exercise Jika diberikan deretan $10$ matriks untuk dikalikan, ada berapa banyak cara mengalikan matriks-matriks tersebut?
	
	\Exercise Buatlah sebuah fungsi yang mengimplementasikan Persamaan~\ref{eq:jumlah-kemungkinan-perkalian-matriks}. Apa masukan dan keluaran dari fungsi yang anda buat?
	
	\Exercise Pergunakan algoritma Warshall untuk memperlihatkan \emph{transitive closure} dari suatu graf berarah yang direpresentasi dengan matriks \emph{adjacency} sebagai berikut:
	\[
	\left[
	\begin{array}{cccc}
		0 & 1 & 0 & 0 \\
		0 & 0 & 1 & 0 \\
		0 & 0 & 0 & 1 \\
		0 & 0 & 0 & 0 \\
	\end{array}
	\right]
	\]
	
	\Exercise Hitunglah kompleksitas algoritma Warshall.
	
	\Exercise \label{ex:all-pairs-shortest-path-floyd} Dengan menggunakan algoritma Floyd, hitunglah jarak terpendek dari setiap pasangan verteks dari suatu graf berarah yang direpresentasikan dengan matriks \emph{adjacency} berikut.
	\[
	\left[
	\begin{array}{ccccc}
		0 & 2 & \infty & 1 & 8 \\
		6 & 0 & 3 & 2 & \infty \\
		\infty & \infty & 0 & 4 & \infty \\
		\infty & \infty & 2 & 0 & 3 \\
		3 & \infty & \infty & \infty 0 \\
	\end{array}
	\right]
	\]
	
	\Exercise Mengapa entri diagonal pada algoritme Floyd diberi nilai $0$? Apakah untuk sembarang graf hal ini selalu dilakukan? Jika ada, tunjukkan sebuah graf yang memiliki matriks \emph{adjacency} dengan diagonal utama tidak $0$.
	
	\Exercise Bagaimana bentuk matriks yang dihasilkan setelah menjalankan algoritme Floyd pada sebuah graf tidak berarah? Mengapa hal ini bisa terjadi?
	
	\Exercise \label{ex:all-pairs-shortest-path-dijkstra} Hitung kompleksitas pencarian \emph{all pairs shortest path} pada contoh Soal~\ref{ex:all-pairs-shortest-path-floyd} jika menggunakan algoritme Dijkstra untuk setiap verteks dalam graf.
\end{ExerciseList}
